home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / BARNET / COMPILER / SATHER / !Sather / Library / Graphs / sa / ugraph < prev    next >
Text File  |  1996-07-13  |  8KB  |  231 lines
  1. ---------------------------> Sather 1.1 source file <--------------------------
  2. -- Author: Benedict A. Gomes <gomes@tiramisu.ICSI.Berkeley.EDU>
  3. -- COPYRIGHT NOTICE: This code is provided WITHOUT ANY WARRANTY
  4. -- and is subject to the terms of the SATHER LIBRARY GENERAL PUBLIC
  5. -- LICENSE contained in the file: Sather/Doc/License of the
  6. -- Sather distribution. The license is also available from ICSI,
  7. -- 1947 Center St., Suite 600, Berkeley CA 94704, USA.
  8. -------------------------------------------------------------------
  9. class UGRAPH{NTP} < $UGRAPH{NTP} is
  10.    -- For now, call this UGRAPH since we have no other graph
  11.    -- implementations.
  12.    -- A basic undirected graph implemented with a hash table from
  13.    -- nodes to neighbors. This implementation
  14.    -- mainly specifies the access routines. 
  15.    include UGRAPH_INCL{NTP};
  16.    
  17.    private attr node_list: FLIST{NTP};
  18.    private attr neighbor_map: FMAP{NTP,FLIST{NTP}};
  19.    -- holds mappings from each node to all it's neighbors
  20.    
  21.    private attr node_generator: $SUCC_STREAM{NTP}; -- Generator of nodes
  22.    -- which is used by add_node. If a node generator is not provided
  23.    -- at creation time, then add_node cannot be used, since the graph
  24.    -- does not know how to create new unique nodes.
  25.    
  26.    -- ------------------- Initialization ------------------
  27.    create: SAME is 
  28.       -- All the data structures can be initialized with void
  29.       res ::= new;
  30.       res.neighbor_map := #FMAP{NTP,FLIST{NTP}};
  31.       res.node_list := #;
  32.       return(res) 
  33.    end;
  34.  
  35.    create(node_gen: $SUCC_STREAM{NTP}): SAME pre ~void(node_gen) is
  36.       -- Create a new ugraph. Store "node_gen" as a generator
  37.       -- of nodes, so that when "add_node: NTP" is called it
  38.       -- can generate unique new nodes. 
  39.       res: SAME := create;
  40.       res.node_generator := node_gen;
  41.       return res;
  42.    end;
  43.    
  44.    copy: SAME is 
  45.       res ::= #SAME;
  46.       loop res.add_node(node!) end;
  47.       loop res.connect(edge!) end;
  48.       return res;
  49.    end;
  50.  
  51.    -- ------------------- Insertion -----------------------
  52.    add_node: NTP is
  53.       -- Add a new node and return the index
  54.       if void(node_generator) then
  55.      raise #GRAPH_EXC(self,"add_node",self,
  56.               "Cannot call add_node: NTP on this graph."
  57.               " No node generator was provided");
  58.       else
  59.      -- Get the next unique node
  60.      n: NTP := node_generator.next; 
  61.      -- If it is really unique, add it to the list
  62.      assert ~has_node(n);
  63.      add_node(n);
  64.      return n;
  65.       end;      
  66.    end;
  67.    
  68.    add_node(n: NTP):NTP pre ~test_node(n) is
  69.       -- Replaces an existing node that is the same as "n"
  70.       -- This function is guaranteed to return the same node, "n"
  71.       -- though this is not true of graph implementations in general
  72.       node_list := node_list.push(n);
  73.       neighbor_map := neighbor_map.insert(n,#FLIST{NTP});
  74.       return n;
  75.    end;
  76.  
  77.    add_node(n: NTP) is
  78.       -- Add a node "n". 
  79.       -- 
  80.       -- Technical detail: Since the node index for "n" is the
  81.       -- same as the node for this particular implementation, 
  82.       -- there is no need to return a value. Note that this function
  83.       -- is not in the graph abstraction
  84.       discard ::= add_node(n);
  85.    end;
  86.    
  87.    connect(n1,n2: NTP) is
  88.       -- Connect n1 and n2. Add the nodes if they do not exist
  89.       if test_edge(n1,n2) then return; end;
  90.       if ~test_node(n1) then add_node(n1) end;
  91.       if ~test_node(n2) then add_node(n2) end;
  92.       add_neighbor(n1,n2);
  93.    end;
  94.  
  95.    -- ------------------- Removal -------------------------
  96.    delete_node(n: NTP) is
  97.       -- Delete a node from the graph, and all its accompanying edges
  98.       node_list.delete(node_list.index_of(n));
  99.       neighbor_map := neighbor_map.delete(n);
  100.    end;
  101.  
  102.    disconnect(n1,n2: NTP)  pre test_node(n1) and test_node(n2) is
  103.       -- Deletes the edge between n1 and n2 if it exists 
  104.       n1list ::= neighbor_list(n1);
  105.       n2list ::= neighbor_list(n2);
  106.       neighbor_map := neighbor_map.insert(n1,n1list.delete_elt(n2));
  107.       neighbor_map := neighbor_map.insert(n2,n2list.delete_elt(n1));
  108.    end;
  109.  
  110.    -- ------------------- Comparison ----------------------
  111.    is_identical(g: SAME): BOOL is
  112.       -- Check whether the two graphs have the same nodes, edges in
  113.       -- the same order
  114.       if g.n_nodes /= n_nodes then return false end;
  115.       loop  if ~elt_eq(node!,g.node!) then return false end end;
  116.       loop n::= node!;
  117.      if ~neighbor_map.get(n).equals(g.neighbor_map.get(n)) then 
  118.         return false 
  119.      end;
  120.       end;
  121.       return true
  122.    end;
  123.  
  124.    -- ------------------- Transformation ------------------
  125.    permute_nodes(new_positions: $MAP{NTP,INT}) is
  126.       -- Permute the nodes of the graph so that they will
  127.       -- be yielded in the order expressed by "new_positions"
  128.       perm_arr: ARRAY{INT} := #(node_list.size);
  129.       loop perm_arr.set!(new_positions[node_list.elt!]) end;
  130.       new_src: FLIST{NTP} := #(node_list.size);
  131.       loop new_src := new_src.push(node_list.elt!) end;
  132.       permute_alg: A_PERMUTE{NTP,FLIST{NTP}};
  133.       permute_alg.permute_into(new_src,perm_arr,node_list);
  134.       -- node_list.permute(perm_arr);
  135.    end;
  136.  
  137.    sort is
  138.       -- Reduce the graph to a canonical form based on the
  139.       -- sorting order of nodes and edges
  140.       sorter:A_SORT{NTP,FLIST{NTP}};
  141.       sorter.sort(node_list);
  142.       loop n ::= node_list.elt!;                      -- Sort edges
  143.      neighbors ::= neighbor_map.get(n);
  144.      sorter.sort(neighbors);
  145.       end;
  146.    end;
  147.  
  148.    -- ------------------- Implementation ------------------
  149.    test_node(n: NTP): BOOL is return neighbor_map.test(n) end;
  150.    
  151.    n_nodes: INT is return node_list.size end;
  152.  
  153.    node!: NTP is loop yield node_list.elt! end; end;
  154.  
  155.    test_edge(s,t: NTP): BOOL is
  156.       if ~test_node(s) or ~test_node(t) then return false
  157.       else return neighbor_map.get(t).contains(s);   end;
  158.    end;
  159.    
  160.    n_adjacent(n: NTP): INT pre test_node(n) is 
  161.       return(neighbor_map.get(n).size);
  162.    end;
  163.    
  164.    adjacent!(once n: NTP): NTP pre check_node(n,"adjacent!") is
  165.       neighbors ::= neighbor_map.get(n);
  166.       loop yield neighbors.elt! end;
  167.    end;
  168.          
  169.    new_edge(n1,n2: NTP): UEDGE{NTP} is return #UEDGE{NTP}(n1,n2) end;
  170.    
  171.    edge!: UEDGE{NTP} is
  172.       -- Return all edges in the graph. A problem, since we represent
  173.       -- edges in both directions. We might want to either maintain
  174.       -- a hash table of edges already seen or generate a matching
  175.       -- or something of the sort.
  176.       -- Or can use some arbitrary test to choose one or the other.
  177.       -- such as lt
  178.       -- For now, use a set which holds all nodes for which all edges
  179.       -- have been yielded
  180.       seen: FSET{NTP} := #;    -- Holds all nodes that have had their
  181.       -- edges yielded
  182.       loop n1 ::= node_list.elt!;
  183.      n1_neighbors ::= neighbor_map.get(n1);
  184.      loop n2 ::= n1_neighbors.elt!;
  185.         if ~seen.test(n2) then yield new_edge(n2,n1); end;
  186.      end;
  187.      seen := seen.insert(n1);
  188.       end;
  189.    end;
  190.  
  191.    -- ----------------------- Private accessing functions ---------------
  192.    private check_node(n: NTP,routine_name: STR): BOOL is
  193.       if test_node(n) then return true 
  194.       else 
  195.      #ERR+routine_name+" received a node not in the graph\n";
  196.      return false;
  197.       end;
  198.    end;
  199.  
  200.    private add_neighbor(n1,n2: NTP) is
  201.      neighbor_map:=neighbor_map.insert(n1,neighbor_map.get(n1).push(n2));
  202.      neighbor_map:=neighbor_map.insert(n2,neighbor_map.get(n2).push(n1));
  203.    end;
  204.  
  205.    private neighbor_list(n1:NTP):FLIST{NTP} is
  206.       return neighbor_map.get(n1) 
  207.    end;
  208.  
  209.    --   sort_by(lt: ROUT{NTP,NTP}:BOOL) is
  210.       -- Reduce the graph to a cannoical form using the predicate "lt"
  211.       -- to determine the less than relation between two nodes
  212.       --      ARR_ALG{NTP,FLIST{NTP}}::sort_by(node_list,lt); 
  213.       -- Sort edges
  214.       --      loop n ::= node_list.elt!;
  215.       --     neighbors ::= neighbor_map.get(n);
  216.       --     ARR_ALG{NTP,FLIST{NTP}}::sort_by(neighbors,lt);
  217.       --      end;
  218.       --   end;
  219.  
  220.    --   create_from(g: $GRAPH{NTP}): SAME is
  221.    --      -- Return a graph created from "g"
  222.    --      res ::= #;
  223.    --      loop res.add_node(g.node!) end;
  224.    --      loop res.add_edge(g.edge!) end;
  225.    --      return(res);
  226.    --   end;
  227.  
  228.  
  229. end;
  230. ---------------------------------------------------------------  
  231.